package com.linchong.sort;

import java.util.Arrays;
import java.util.Stack;

/**
 * @BelongsProject:Algorithm
 * @BelongsPackage:com.linchong.sort
 * @Author:linchong
 * @CreateTime:2019-01-04 22:12
 * @Description:快速排序
 * 递归版本 PK 非递归版本
 *
 * 思想：分治，1.选取基准点；2.划分区间；3.递归/重复
 * 平均时间复杂度：O(nlogn)
 * 最坏时间复杂度：O(n*n)   #最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录,
 * 快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的
 * 比较次数达到最大值：Cmax= n(n-1)/2=O(n2)
 *
 * 最好时间复杂度：O(nlogn)
 *
 * 空间复杂度：若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，
 * 递归树的高度为O(n)，所需的栈空间为O(n)。
 *
 * 稳定性：不稳定
 * 是否受初始数据影响：受，快速排序法与主元的选择有关，若一般选子序列左侧第一个元素比较，则第一个元
 * 素最好是大小居中的，以使得分成的两个子数组长度大致相等，性能才能最佳，所以快速排序也与初始输入集有关的
 *
 */
public class QuickSort {
    static int res = -1;
    public static void quickSort(int[] arr,int n){
        quick_sort(arr,0,n-1);
    }

    private static void quick_sort(int[] arr, int l, int r) {
        if(l>=r) return;
        swap(arr, l + (int) (Math.random() * (r - l + 1)), r);  //优化
        int position = partition(arr,l,r);
        if(position==4){
            res = arr[position];
        }
        quick_sort(arr,l,position-1);
        quick_sort(arr,position+1,r);
    }

    private static void swap(int[] arr, int i, int r) {
        int temp = arr[i];
        arr[i] = arr[r];
        arr[r] = temp;
    }

    //返回已确定位置数的下标
    private static int partition(int[] arr, int l, int r) {
        int pivot = arr[r];           //选基准值
        //i区间为排好序的区间[0-i-1]<pivot与[i-r]>=pivot
        int i = l;
        for(int j = l;j<=r-1;j++){
            if(arr[j]<pivot){         //分割序列
                swap(arr,j,i);
                i = i+1;
            }
        }
        swap(arr,i,r);
        return i;
    }

    //非递归版本
    // start和end为前闭后闭
    private static void nonRec_quickSort(int[] a, int start, int end) {
        // 用栈模拟
        Stack<Integer> stack = new Stack<>();
        if (start < end) {
            stack.push(end);
            stack.push(start);
            while (!stack.isEmpty()) {
                int l = stack.pop();
                int r = stack.pop();
                int index = partition(a, l, r);
                if (l < index - 1) {
                    stack.push(index - 1);
                    stack.push(l);
                }
                if (r > index + 1) {
                    stack.push(r);
                    stack.push(index + 1);
                }
            }
        }
        System.out.println(Arrays.toString(a));
    }
    private static int partition2(int[] a, int start, int end) {
        int pivot = a[start];
        while (start < end) {
                                //右到左，找出第一个小于给定基准值的元素位置，将其放到start位置
            while (start < end && a[end] >= pivot)
                end--;
            a[start] = a[end]; //左到右，找出第一个大于给定基准值的元素位置
            while (start < end && a[start] <= pivot)
                start++;
            a[end] = a[start];
        }
        a[start] = pivot;
        return start;
    }

    public static void main(String[] args) {
        int[] arr = {1,6,3,5,4,12,24,16};
        quickSort(arr,arr.length);
       // nonRec_quickSort(arr,0,arr.length-1);
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();
        System.out.println("jieguo:"+res);
    }
}
